package edu.java.homework.hw05;

public class Labyrinth {

    /**
     * @param args
     */
  
   static  int[][] labMatrix={	{1,1,1,0,0,1,0},
	    			{0,1,1,0,0,0,0},
	    			{1,0,1,0,1,0,0},
	    			{0,0,0,0,1,0,1},
	    			{0,1,1,0,0,0,0},
	    			{0,0,0,0,0,1,1}};
    static int endI=4;
    static int endJ=6;
    static boolean result=false;
    public static void main(String[] args) {
	int startI=3;
	int startJ=2;
	lab(startI,startJ);
	System.out.println("There is a path y/n?   " + result);

    }
    
    public static void lab(int i, int j){
	int row=labMatrix.length;
	int col=labMatrix[0].length;
	// if 'i' and 'j' are out of the dimention of the matrix
	if(i<0||i==row||j<0||j==col){
	    return;
	}
	// if we fall in '1'
	if(labMatrix[i][j]==1){
	    return;
	}
	// if element is visited --> return
	if(labMatrix[i][j]==2){
	    return;
	}
	// if we catch the end element
	if(i==endI&&j==endJ){
	   result=true;
	   return;
	}
	//mark the element as visited
	labMatrix[i][j]=2;
	
	// recursion calls
	lab(i-1,j);	// up
	lab(i+1,j);	//down
	lab(i,j-1);	//left
	lab(i,j+1);	//right
	
	// backtracking; revise the visited elements when we back
	labMatrix[i][j]=0;
    }

}
